package com.wj.graph;

import com.wj.linear.Queue;
import com.wj.tree.IndexMinPriorityQueue;

import java.util.Arrays;

/**
 * Dijkstra算法
 * @author wen.jie
 * @date 2021/8/30 15:14
 */
public class DijkstraSP {

    //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private DirectedEdge[] edgeTo;

    //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    private double[] distTo;

    //存放树中顶点与非树中顶点之间的有效横切边
    private IndexMinPriorityQueue<Double> pq;

    public DijkstraSP(EdgeWeightedDigraph G, int s){
        this.edgeTo = new DirectedEdge[G.V()];
        this.distTo = new double[G.V()];
        Arrays.fill(distTo, Double.POSITIVE_INFINITY);
        pq = new IndexMinPriorityQueue<>(G.V());

        distTo[s] = 0.0;
        pq.insert(s, 0.0);
        while (!pq.isEmpty()) {
            relax(G, pq.delMin());
        }
    }

    //松弛图G中的顶点v
    private void relax(EdgeWeightedDigraph G, int v){
        for (DirectedEdge edge : G.adj(v)) {
            int w = edge.to();
            //松弛技术
            if (distTo(v) + edge.weight() < distTo(w)){
                distTo[w] = distTo[v] + edge.weight();
                edgeTo[w] = edge;
                if (pq.contains(w)) {
                    pq.changeItem(w, distTo(w));
                } else {
                    pq.insert(w, distTo(w));
                }
            }
        }
    }

    //获取从顶点s到顶点v的最短路径的总权重
    public double distTo(int v){
        return distTo[v];
    }

    //判断从顶点s到顶点v是否可达
    public boolean hasPathTo(int v){
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    //查询从起点s到顶点v的最短路径中所有的边
    public Queue<DirectedEdge> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }
        Queue<DirectedEdge> allEdges = new Queue<>();
        while (true) {
            DirectedEdge e = edgeTo[v];
            if (e == null)
                break;
            allEdges.enqueue(e);
            v = e.from();
        }
        return allEdges;
    }

}
